A randomized blocked algorithm for efficiently computing rank-revealing factorizations of matrices

摘要

This manuscript describes a technique for computing partial rank-revealingfactorizations, such as, e.g, a partial QR factorization or a partial singularvalue decomposition. The method takes as input a tolerance $\varepsilon$ and an$m\times n$ matrix $A$, and returns an approximate low rank factorization of$A$ that is accurate to within precision $\varepsilon$ in the Frobenius norm(or some other easily computed norm). The rank $k$ of the computedfactorization (which is an output of the algorithm) is in all examples weexamined very close to the theoretically optimal $\varepsilon$-rank. Theproposed method is inspired by the Gram-Schmidt algorithm, and has the same$O(mnk)$ asymptotic flop count. However, the method relies on randomizedsampling to avoid column pivoting, which allows it to be blocked, and henceaccelerates practical computations by reducing communication. Numericalexperiments demonstrate that the accuracy of the scheme is for every matrixthat was tried at least as good as column-pivoted QR, and is sometimes muchbetter. Computational speed is also improved substantially, in particular onGPU architectures.